The present invention relates generally to data processing systems, and relates more particularly to the management of hardware and software components of data processing systems. Specifically, the present invention provides a method and apparatus for automatic allocation of computing resources amongst multiple entities that obtain value by utilizing the resources to perform computation.
The problem of how to optimally allocate a limited set of resources amongst multiple entities that use or consume the resources has been extensively studied in disciplines including economics, manufacturing, telecommunications networks, and computing systems. Within the latter domain, the recent evolution of highly interconnected, rapidly changing, distributed computing systems such as the Internet has made it increasingly important to be able to rapidly compute and execute resource allocation decisions in an automated fashion.
Traditional approaches to provisioning and capacity planning typically aim to achieve an extremal value of some overall system performance metric (e.g., maximum average throughput or minimum average response time). Other conventional techniques employ market-based mechanisms for resource allocation (e.g., auction bidding or bilateral negotiation mechanisms). For example, a commonly used approach has been to anticipate the maximum possible load on the system, and then perform one-time static allocation of resources capable of handling the maximum load within a specified margin of safety. A common problem with such approaches is that, with modern workloads such as hit rates on Web pages, the demand rate may vary dynamically and rapidly over many orders of magnitude, and a system that is statically provisioned for its peak workload may spend nearly all its time sitting idle.
Thus, there is a need in the art for a method and apparatus for dynamic resource allocation in distributed computing systems.